//删除字符串中的所有相邻重复项
class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for (auto& c : s) {
            if (ret.empty() || ret.back() != c)
                ret.push_back(c);
            else
                ret.pop_back();
        }
        return ret;
    }
};

// 字符串相乘
class Solution {
public:
    string multiply(string num1, string num2) {
        if (num2[0] == '0' || num1[0] == '0')
            return "0";
        string ret;
        int m = num1.size();
        int n = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int> temp(m + n - 1);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                temp[i + j] += (num1[i] - '0') * (num2[j] - '0');

        int t = 0, cur = 0;
        while (cur < m + n - 1 || t) {
            if (cur < m + n - 1)
                t += temp[cur++];
            ret += (t % 10 + '0');
            t /= 10;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

class Solution {
public:
    string add_string(string s1, string s2) {
        int t = 0;
        int n1 = s1.size();
        int n2 = s2.size();
        int i = 0, j = 0;
        string ret;
        while (t || i < n1 || j < n2) {
            int sum = 0;
            if (i < n1) {
                sum += (s1[i] - '0');
                i++;
            }
            if (j < n2) {
                sum += (s2[j] - '0');
                j++;
            }
            if (t)
                sum++;
            if (sum >= 10) {
                t = 1;
            } else {
                t = 0;
            }
            ret += (sum % 10 + '0');
        }
        return ret;
    }
    string multiply(string num1, string num2) {
        if (num1[0] == '0' || num2[0] == '0')
            return "0";
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int n1 = num1.size();
        int n2 = num2.size();
        string ret("0");
        for (int i = 0; i < n1; i++) {
            if (num1[i] == '0')
                continue;
            int add = 0;
            string temp;
            for (int k = 0; k < i; k++)
                temp += '0';
            int x = num1[i] - '0';
            for (int j = 0; j < n2; j++) {
                int y = num2[j] - '0';
                int sum = x * y + add;
                temp += (sum % 10 + '0');
                add = sum / 10;
            }
            while (add) {
                temp += (add % 10 + '0');
                add /= 10;
            }
            ret = add_string(temp, ret);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};